Computer memory operating speed and cost bear a generally inverse relationship. Due to the tendency of computer programs to use (read from or write to) the same memory addresses repeatedly, stratified memory architectures, in which a relatively large but slow main memory is augmented with a relatively fast but small cache memory, have become commonplace. When a processor reads from a memory address, the data stored in that address in main memory are copied to the cache memory. When a processor writes to a memory address, the data are written at least to the cache memory. In either case, subsequent use of the same address may then be made with respect to the cache memory at typically far greater speed. Stratified memory architectures, if properly designed, are “transparent” to the processor and the computer programs.
Tags associate cache addresses, typically lines in the cache memory, with main memory addresses. Tags tend to be long. Consequently, tags require substantial memory, making them expensive and power consumptive to store.